package gold.digger;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC825 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int numFriendRequests(int[] ages) {
            int ans = 0;
            Map<Integer, Integer> map = new HashMap<>();
            // 统计岁数对应的数量
            for (int age : ages) {
                map.put(age, map.getOrDefault(age, 0) + 1);
            }

            // a >= b > 0.5 * a + 7
            // a > 0.5 * a + 7
            // a > 14
            for (int a = 15; a < 121; a++) {
                if (!map.containsKey(a)) continue;
                // b岁的取值范围为：0.5 * a + 7 < b <= a
                for (int b = a / 2 + 7 + 1; b < a; b++) {
                    // n个a岁和m个b岁能交朋友
                    ans += map.getOrDefault(a, 0) * map.getOrDefault(b, 0);
                }
                // n个a岁和n-1个a岁之间能交朋友
                ans += map.getOrDefault(a, 0) * (map.getOrDefault(a, 0) - 1);
            }
            return ans;
        }
    }

    public void run() {
        Solution solution = new Solution();
//        int[] arr = {16, 16};
        int[] arr = {16, 17, 18};
        System.out.println(solution.numFriendRequests(arr));
    }

    public static void main(String[] args) throws Exception {
        LC825 an = new LC825();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
